#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string.h>
// 求数组长度
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
// 交换数组中的两个元素
#define SWAP(arr, i, j ) {			\
	int tmp = arr[i];			\
	arr[i] = arr[j];			\
	arr[j] = tmp;			\
}

void print_arr(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

// 核心操作: 堆化
static void heapify(int arr[], int heap_len, int idx) {
	/*
		写循环不知道怎么写,可以先写个死循环
		然后逐渐深入到循环中,找到循环结束的条件
		这个条件大概率是某个else,在else当中break
	*/
	while (1){
		// 1.根据父结点,算出左右节点的下标
		int lchild_idx = (idx << 1) + 1;
		int rchild_idx = (idx << 1) + 2;
		// 先假设最大值的下标就是父结点的下标
		int max_idx = idx;

		// 如果左子树存在且是最大值,左子树下标就成为新的最大值下标
		if (lchild_idx < heap_len && arr[lchild_idx] > arr[max_idx]) {
			max_idx = lchild_idx;
		}
		// 如果右子树存在且是最大值,右子树下标就成为新的最大值下标
		if (rchild_idx < heap_len && arr[rchild_idx] > arr[max_idx]) {
			max_idx = rchild_idx;
		}

		// 如果此时最大值索引不是父节点索引,就交换父节点和此子树结点的值
		if (max_idx != idx) {
			SWAP(arr, max_idx, idx);
			// 交换成功了,堆化没有结束,还需要继续以max_idx为heapify的idx索引继续堆化操作
			idx = max_idx;
		}
		else {
			// 父节点已经是最大结点了,此时以idx为父节点的堆已经是大顶堆了,堆化完成了
			break;
		}
	}
}

static void build_heap(int arr[], int len) {
	// 1.自上而下,最后一个非叶子的结点的下标
	int last_idx = len - 2 >> 1;
	// 2.从最后一个非叶子结点开始遍历,直到根节点,都以它们的结点为父节点构建大顶堆
	for (int i = last_idx; i >= 0; i--) {
		heapify(arr, len, i);
	}
	printf("first heap: ");
	print_arr(arr, len);
}

void heap_sort(int arr[], int len) {
	// 1.将原始数组构建成大顶堆
	build_heap(arr, len);

	// 2.反复移除大顶堆的堆顶元素,然后再重建大顶堆
	int heap_len = len;     // 大顶堆的逻辑长度,一开始就是数组的长度
	while (heap_len > 1) {
		SWAP(arr, 0, heap_len - 1);
		heap_len--;
		/*
			堆排序的核心操作:重新构建大顶堆
			为了让该函数实现复用, 把该函数设计成:
			以idx索引的元素为父结点,堆的逻辑长度是len,然后构建大顶堆
		*/
		heapify(arr, heap_len, 0);
		print_arr(arr, len);
	}
}

int main(void) {
	int arr[] = { 4, 10, 3, 5, 1, 10, 20, 30};
	int len = ARR_LEN(arr);
	print_arr(arr, len);
	heap_sort(arr, len);
	return 0;
}